46. 全排列

发表于 | 分类于 | 阅读次数：

链接：https://leetcode-cn.com/problems/permutations/

题目描述

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

题目分析

本题简单的回溯法即可解决。

递归结构

其中w为任选的一个数

递归边界

1
if(n == len(list))

递归参数

  • n: 当前走到哪一步了
  • list：输入集合
  • result：单个返回结果
  • result_all 最终返回结果

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def __init__(self):
        self.result_all = None
        self.visited = None
    
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.result_all = []
        self.visited = [0 for _ in range(len(nums))]
        self.dfs(0, nums, [])
        return self.result_all
        
    def dfs(self, n, nums, result):
        if n == len(nums):
            self.result_all.append(result[:])
            return
        
        for i, num in enumerate(nums):
            if self.visited[i] == 1:
                continue
            result.append(num)
            self.visited[i] = 1
            self.dfs(n + 1, nums, result)
            result.pop()
            self.visited[i] = 0